package 剑指offer;

public class 剑指Offer07重建二叉树 {
    //将index和遍历的数组抽取出来，可以不用每次都将其带入到方法的参数内，减少代码量
    private int index;//用来辅助遍历preorder的各个节点
    private int[] preorder;//用来保存先序遍历的数组
    private int[] inorder;//用来保存中序遍历的数组
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return buildTreeHelp(0,inorder.length - 1);//通过这个help方法，就可以将数组转换为字符串
    }

    /**
     * 给我先序和中序遍历的数组，我就可以还原改树。
     * @param left 中序遍历的数组的左位置下标
     * @param right 中序遍历的数组的右位置的下标
     * @return 返回根节点。
     */
    private TreeNode buildTreeHelp( int left, int right) {
        //递归终止条件
        if (left > right) return null;//如果在中序遍历的结果中，left > right ，则说明不合法，直接返回null；
        if (index > preorder.length) return null;//如果在先序遍历数组时，index下标大于数组下标，越界返回null；
        TreeNode root = new TreeNode(preorder[index]);//否则就以当前节点的值作为根节点
        int pos = find((Integer)root.val,inorder);//找到当前节点在中序遍历的位置
        root.left = buildTreeHelp(left,pos - 1);//将pos以前的数，作为当前节点的左子树
        root.right = buildTreeHelp(pos+1,right);//将pos右边的数，作为右子树
        return  root;//最终返回根节点
    }
    private int find(int val,int[] inorder){
        for (int i = 0; i < inorder.length; i++) {
            if (val == inorder[i]) return i;
        }
        return -1;
    }
}
